package william.tree;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * @author ZhangShenao
 * @date 2024/3/21
 * @description <a href="https://leetcode.cn/problems/path-sum-iii/description/?envType=study-plan-v2&envId=top-100-liked">...</a>
 */
public class Leetcode437_路径总和3 {
    private class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    /**
     * 采用递归算法实现
     * 类似穷举法,对二叉树进行递归dfs遍历,计算从每个节点出发,能够组成目标和数量,并将结果相加,然后再递归处理左、右子树
     * <p>
     * 时间复杂度 O(N^2) 对二叉树进行双重遍历
     * 空间复杂度 O(N) 递归栈空间
     */
    public int pathSum(TreeNode root, int targetSum) {
        //递归终止条件
        if (root == null) {
            return 0;
        }

        //对二叉树进行dfs深度优先遍历,针对每一个节点,计算以该节点为起点满足targetSum的路径数量,并将结果累加
        int count = rootSum(root, targetSum);

        //递归处理左、右子树
        count += pathSum(root.left, targetSum);
        count += pathSum(root.right, targetSum);

        //返回累加结果
        return count;
    }

    /**
     * 递归实现
     * 计算以root为起点,满足targetSum的路径数量
     */
    private int rootSum(TreeNode root, long targetSum) {
        //递归终止条件
        if (root == null) {
            return 0;
        }

        //判断当前路径是否满足
        int count = 0;
        if (targetSum == root.val) {
            ++count;
        }

        //递归累加左、右子树的路径
        long remains = targetSum - root.val;
        count += rootSum(root.left, remains);
        count += rootSum(root.right, remains);

        //返回累计数量
        return count;
    }

}
